Матч 353, Словарь (Glossary)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Словарь состоит из списка терминов в алфавитном порядке. По заданному набору терминов необходимо построить словарь согласно следующим правилам. Для каждой буквы от ‘A’ до ‘Z’, для которой есть начинающийся с нее термин, следует создать блок, состоящий из следующих строк:

1. Первая строка содержит букву в верхнем регистре.

2. Вторая строка содержит 19 символов ‘-‘.

3. Далее располагаются термины, начинающиеся с текущей буквы в алфавитном порядке без учета регистра. Каждому термину должны предшествовать два пробела.

4. Добавить к каждой строке справа пробелы так, чтобы длина каждой строки равнялась 19 символам.

Блоки букв сортируем в алфавитном порядке и разбиваем на две колонки. Левая колонка содержит блоки для букв от ‘A’ до ‘M’, правая – блоки для букв от ‘N’ до ‘Z’. Ширина каждой колонки составляет 19 символов, колонки разделяют два пробела.

Класс: Glossary

Метод: vector<string> buildGlossary(vector<string> items)

Ограничения: -100 £ x1, y1, x2, y2 £ 100, 1 £ d £ 200.

Вход. Координаты фокусов (x₁, y₁), (x₂, y₂) и сумма расстояний от точек эллипса до фокусов d.

Выход. Количество точек с целочисленными координатами, лежащих строго внутри эллипса.

Пример входа

items

{"Canada", "France", "Germany", "Italy", "Japan", "Russia",

"United Kingdom", "United States"}

{"alpha", "beta", "gamma", "delta", "omega"}

{"AVL tree", "backtracking", "array", "balanced tree", "binary search"}

Пример выхода

{"C R ",

"------------------- -------------------",

" Canada Russia ",

"F U ",

"------------------- -------------------",

" France United Kingdom ",

"G United States ",

"------------------- ",

" Germany ",

"I ",

"------------------- ",

" Italy ",

"J ",

"------------------- ",

" Japan " }

{"A O ",

"------------------- -------------------",

" alpha omega ",

"B ",

"------------------- ",

" beta ",

"D ",

"------------------- ",

" delta ",

"G ",

"------------------- ",

" gamma " }

{"A ",

"------------------- ",

" array ",

" AVL tree ",

"B ",

"------------------- ",

" backtracking ",

" balanced tree ",

" binary search " }

РЕШЕНИЕ

обработка строк

Отсортируем термины в массиве items в алфавитном порядке без учета регистра, используя функцию сравнения cmp. Проходим по словам, формируем требуемые блоки строк для каждой буквы. Для букв ‘A’ – ‘M’ требуемые строки заносим в массив col[0], для букв ‘N’ – ‘Z’ – в массив col[1]. Выравниваем массивы col[0] и col[1] по количеству элементов, после чего сливаем их так, чтобы образовалось две колонки.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

string add(string s, int size)

{

return s + string(size - s.size(),' ');

}

int cmp(string a, string b)

{

int i;

for(i = 0; i < a.size(); i++) a[i] = tolower(a[i]);

for(i = 0; i < b.size(); i++) b[i] = tolower(b[i]);

return a < b;

}

class Glossary

{

public:

vector<string> buildGlossary(vector<string> items)

{

vector<string> col[2];

int pos = 0, i;

char c, last = ' ';

sort(items.begin(),items.end(),cmp);

for(i = 0; i < items.size(); i++)

{

c = toupper(items[i][0]);

if(c != last)

{

pos = (c >= 'N');

col[pos].push_back(add(string(1,c),19));

col[pos].push_back(string(19,'-'));

last = c;

}

col[pos].push_back(add(" "+items[i],19));

}

while (col[0].size() < col[1].size()) col[0].push_back(string(19, ' '));

while (col[1].size() < col[0].size()) col[1].push_back(string(19, ' '));

for (i = 0; i < col[0].size(); i++)

col[0][i] = col[0][i] + " " + col[1][i];

return col[0];

}

};